package other

import (
	"gitee.com/ChanYeung/go-utils/collections"
	"sort"
)

/**
位1的个数
编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明重量）。
*/
func hammingWeight(num uint32) int {
	//1001 9
	//1010 10
	rst := num
	count := 0
	for rst > 0 {
		if (rst & 1) == 1 {
			count++
		}
		rst = rst >> 1 //因为最末尾可能就是1，如果先右移一次，就丢掉了这个1
	}
	return count
}

/**
汉明距离
两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。

给你两个整数 x 和 y，计算并返回它们之间的汉明距离。



示例 1：

输入：x = 1, y = 4
输出：2
解释：
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑
上面的箭头指出了对应二进制位不同的位置。

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnyode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/
func hammingDistance(x int, y int) int {
	//x和y都转化为二进制的时候，在相同的位置上如果值都一样，他们的汉明距离就是0。
	//如果在相同的位置上值不一样，有多少个不一样的位置，那么汉明距离就是多少。
	//所以看到这道题，我们应该最容易想到的就是先异或运算，
	//然后再计算这个异或运算的结果在二进制表示中1的个数
	//
	return hammingWeight(uint32(x ^ y))
}

/**
//颠倒给定的 32 位无符号整数的二进制位。

输入：n = 00000010100101000001111010011100
输出：964176192 (00111001011110000010100101000000)
解释：输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
     因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnc5vg/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/
func reverseBits(num uint32) uint32 {
	copyNum := num
	for i := 0; i < 32; i++ {
		//取到最后一位
		x := num & 1
		//num 右移
		num >>= 1
		//copy num 左移1位+ num右移出的一位
		copyNum = (copyNum << 1) | x
	}
	return copyNum
}

/**
杨辉三角
给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。


*/

func YHgenerate(numRows int) [][]int {
	if numRows == 0 {
		return nil
	}
	result := [][]int{{1}}
	if numRows == 1 {
		return result
	}

	for i := 1; i < numRows; i++ {
		level := []int{}
		for k := 0; k < i+1; k++ { //每层都比上一层多一个数
			//上层level的元素个数，判断是否有这个位置元素（下标不越界）
			//左上角数据
			left := 0
			if k-1 >= 0 && k-1 < len(result[i-1]) {
				left = result[i-1][k-1]
			}
			//右上角数据
			right := 0
			if k < len(result[i-1]) {
				right = result[i-1][k]
			}
			level = append(level, left+right) //该层新元素
		}
		result = append(result, level)
	}
	return result
}

/**
有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']'的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
输入：s = "()"
输出：true

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnbcaj/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/
func isValid(s string) bool {
	stack := collections.NewStack()
	for i := 0; i < len(s); i++ {
		uchar := s[i]
		if stack.Peak() == nil { //栈中没有数据
			stack.Push(uchar)
		} else {
			peakChar := stack.Peak().(uint8)
			if (peakChar == '{' && uchar == '}') || (peakChar == '[' && uchar == ']') || (peakChar == '(' && uchar == ')') {
				stack.Pop() //弹出元素
			} else {
				stack.Push(uchar)
			}
		}
	}
	if stack.IsEmpty() {
		return true
	}
	return false
}

/**
缺失数字
给定一个包含 [0, n]中n个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。



示例 1：

输入：nums = [3,0,1]
输出：2
解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。


作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnj4mt/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/

func missingNumber(nums []int) int {
	//比如原先数字是0，1，3 那么我为他补上0，1，2，3那么2就是仅出现一次的数字
	//使用异或运算，将所有值进行异或
	xmp := 0
	for i := 0; i < len(nums); i++ {
		xmp ^= nums[i] ^ (i + 1)
	}
	return xmp
}

func isPalindrome(x int) bool {
	//思考：这里大家可以思考一下，为什么末尾为 0 就可以直接返回 false
	if x < 0 || (x%10 == 0 && x != 0) {
		return false
	}
	revertedNumber := 0
	for x > revertedNumber { //只要反转的数 > x的前半截 说明反转了一半了
		revertedNumber = revertedNumber*10 + x%10
		x /= 10
	}
	//反转一半后的数 与前一半相等 说明是回文
	return x == revertedNumber || x == revertedNumber/10
}

/**
4数之和计算
给你一个由 n 个整数组成的数组nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组[nums[a], nums[b], nums[c], nums[d]]（若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d< n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
*/
func fourSum(nums []int, target int) [][]int {
	sort.Ints(nums) //升序排序之后 更好处理
	var result [][]int
	var traceback func([]int, []int, int, int)
	traceback = func(nums []int, combination []int, tmpSum int, index int) {
		if len(combination) == 4 {
			//终止条件
			if tmpSum == target {
				//四数字之和==target，留下组合结果
				tmp := make([]int, 4)
				copy(tmp, combination) //因为 slice 内部数组是指针引用，所以只能曲线救国
				result = append(result, tmp)
			}
			return
		}
		for i := index; i <= len(nums)-(4-len(combination)); i++ {
			if i > index && nums[i] == nums[i-1] {
				//剪枝1： 去重复
				continue
			}
			if target > 0 && tmpSum+nums[i] > target {
				//剪枝2：
				//当target>0时，前N个数之和已经>target，往后加一定一定不满足了
				return
			}

			traceback(nums, append(combination, nums[i]), tmpSum+nums[i], i+1)
			//回溯  是因为slice的append 思路，无须对结果进行回溯
		}
	}
	traceback(nums, []int{}, 0, 0)
	return result
}

/**
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]
*/

func permuteUnique(nums []int) [][]int {
	//	使用回溯算法
	var result [][]int
	var innerPermute func(int)
	used := make([]bool, len(nums))
	swap := func(arr []int, a, b int) {
		tmp := arr[b]
		arr[b] = arr[a]
		arr[a] = tmp
	}
	sort.Ints(nums)
	innerPermute = func(start int) {
		if start == len(nums)-1 { //完成全排列组合
			tmp := make([]int, len(nums))
			copy(tmp, nums)
			result = append(result, tmp)
			return
		}
		for index := start; index < len(nums); index++ {
			//剪枝，去除 重复元素
			if index > 0 && (nums[index-1] == nums[index]) && !used[index-1] {
				//1 1 2 前两个位置都是1，当第一个1回溯后使用第二个1 可能会产生相同的组合情况
				continue
			}
			used[index] = true
			swap(nums, index, start) //交换元素来模拟排列方式
			innerPermute(start + 1)
			swap(nums, index, start) //回溯
			used[index] = false
		}
	}
	innerPermute(0)
	return result
}

func permuteUnique1(nums []int) [][]int {
	var res [][]int
	used := make([]bool, len(nums))
	sort.Ints(nums)
	var helper func(path []int)

	helper = func(path []int) {
		if len(path) == len(nums) {
			temp := make([]int, len(nums))
			copy(temp, path)
			res = append(res, temp)
			return
		}
		for i := 0; i < len(nums); i++ {
			if i-1 >= 0 && nums[i-1] == nums[i] && !used[i-1] {
				continue
			}
			if used[i] {
				continue
			}
			path = append(path, nums[i])
			used[i] = true
			helper(path)
			path = path[0 : len(path)-1]
			used[i] = false
		}
	}
	helper([]int{})
	return res
}

/**
全排列，不去重
*/
func permute(nums []int) [][]int {
	internalPermuteList := make([][]int, 0)
	var permuteInternal func(nums []int, index int)
	permuteInternal = func(nums []int, index int) {
		if index == len(nums)-1 {
			//下标越界了，所以元素的交换情况已经结束，递归结束
			tmp := make([]int, len(nums))
			copy(tmp, nums)
			internalPermuteList = append(internalPermuteList, tmp)
			return
		}
		for i := index; i < len(nums); i++ {
			swapNew(nums, i, index)
			permuteInternal(nums, index+1)
			swapNew(nums, index, i) //回溯，子结果不影响 父结果
		}
	}
	permuteInternal(nums, 0)
	return internalPermuteList
}

func swapNew(nums []int, a, b int) {
	if a != b {
		nums[a] = nums[a] + nums[b]
		nums[b] = nums[a] - nums[b]
		nums[a] = nums[a] - nums[b]
	}
}

/**
接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。


*/
func trap(height []int) int {
	if len(height) == 0 {
		return 0
	}
	var min func(int, int) int
	var max func(int, int) int
	min = func(a, b int) int {
		if a < b {
			return a
		}
		return b
	}
	max = func(i int, i2 int) int {
		if i > i2 {
			return i
		}
		return i2
	}
	capacity := 0
	if height == nil {
		return 0
	}
	size := len(height)
	leftMax, rightMax := make([]int, size), make([]int, size)
	leftMax[0] = height[0]
	for i := 1; i < size; i++ {
		leftMax[i] = max(height[i], leftMax[i-1])
	}
	rightMax[size-1] = height[size-1]
	for i := size - 2; i >= 0; i-- {
		rightMax[i] = max(height[i], rightMax[i+1])
	}
	for i := 1; i < size-1; i++ {
		//两边的柱子 最矮的也比当前柱子高 才能接水
		capacity += min(leftMax[i], rightMax[i]) - height[i]
	}
	return capacity

}

/*
跳跃游戏 II
给你一个非负整数数组nums ，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
假设你总是可以到达数组的最后一个位置。

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳1步，然后跳3步到达数组的最后一个位置。

*/
func jump(nums []int) int {
	var max func(int, int) int
	max = func(i int, i2 int) int {
		if i > i2 {
			return i
		}
		return i2
	}
	steps := 0   //记录跳跃次数
	bounder := 0 //记录当前可用跳跃数的边界，比如在nums[0]=2 表示下一次起跳最多可以从2的下标开始跳
	maxDistance := 0
	for i := 0; i < len(nums)-1; i++ { //最后一个位置不用跳了
		maxDistance = max(i+nums[i], maxDistance) // 一直检测 在bounder边界内，可以跳跃的最远距离
		if i == bounder {
			//到了跳跃的边界时，必须要跳了,直接到可跳最远处
			bounder = maxDistance
			steps++
		}
	}
	return steps
}
